package outoforder.leetcode;

import org.junit.Test;

import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author shhjiang_001
 * @create 2020-07-04 15:16
 */
public class Solution752 {
    public int openLock(String[] deadends, String target) {
        HashSet<String> deadSet = new HashSet<>();
        for (String s:deadends){
            deadSet.add(s);
        }
        LinkedList<String> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        q.offer("0000");
        visited.add("0000");
        int step = 0;
        while (!q.isEmpty()){
            int size = q.size();
            for (int j = 0; j < size; j++) {
                String poll = q.poll();
                if (deadSet.contains(poll)){
                    continue;
                }
                if (poll.equals(target)){
                    return step;
                }
                for (int i = 0; i < 4; i++) {
                    String plus = plusOne(poll, i);
                    if (!visited.contains(plus)){
                        q.offer(plus);
                        visited.add(plus);
                    }
                    String down = downOne(poll, i);
                    if (!visited.contains(down)){
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    String plusOne(String s,int j){
        char[] ch = s.toCharArray();
        if (ch[j] == '9') ch[j] = '0';
        else
            ch[j]++;
        return new String(ch);
    }
    String downOne(String s,int j){
        char[] ch = s.toCharArray();
        if (ch[j] == '0') ch[j] = '9';
        else
            ch[j]--;
        return new String(ch);
    }

    @Test
    public void test(){
        System.out.println(openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
    }
}
